package com.bootcamp.s2_0922.ds.Exercise._0922_ex1;

/**
 * @program: 35th_2_DS_snowlee
 * @description: find middle element, find loop, find first loop, reverse linked list.
 * @author: Keyu Li
 * @create: 2021-09-22 21:17
 **/

public class LinkedList {
    public static void main(String[] args) {

        Node zs = new Node("zs", null);
        Node ls = new Node("ls", null);
        Node wu = new Node("wu", null);
        Node zl = new Node("zl", null);

        // 单链表
        zs.next = ls;
        ls.next = wu;
        wu.next = zl;

        // zs  -->  ls  --> wu   --> zl  --> aa
        String midValue = getMid(zs);


//        zl.next = ls;
        // zs  -->  ls  --> wu   --> zl  --> ls  ---> wu   ---> zl --->....
        boolean bool = hasCircle(zs);
        System.out.println(bool);


        // 如果有环, 获取环的头结点???
        String value = getHead(zs);
        System.out.println(value);
        System.out.println(hasCircle(zs));


        //反转单链表
        // zs  -->  ls  --> wu   --> zl
        // zl  ---> wu  ---> ls  ---> zs
        // 使用非递归方法
        Node newHead = reLinked(zs);
//        System.out.println(newHead);
        // 使用递归方法
//        reLinkedRecur(zs).next = null;
//        System.out.println(headRecur);

    }

    /**
     * 反转单链表
     *
     * @param zs : 原本链表的头结点
     * @return : 新链表的头结点
     */
    private static Node reLinked(Node zs) {
        // 记录 前pre，当前curr，后续next节点
        Node pre, curr, next;
        pre = null;
        curr = zs;
        // 循环遍历
        while (curr.next != null) {
            next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        curr.next = pre;
        return curr;

        // 使用前插法
    }

    // 以递归方式反转单链表
    // 设置静态变量head存储反转链表后的头节点（即原本尾节点）
    static Node headRecur;

    private static Node reLinkedRecur(Node zs) {
        if (zs.next == null) {
            headRecur = zs;
            return zs;
        }
        reLinkedRecur(zs.next).next = zs;
        return zs;
    }

    /**
     * 如果有环, 获取环的头结点的值
     *
     * @param zs : 链表的头结点
     * @return : 环的头结点
     */
    private static String getHead(Node zs) {
        // 如果链表不存在环，则返回null
        if (!hasCircle(zs)) return null;
        // 自头节点遍历，如果从当前节点断开后，后面的链表不存在环，则说明当前节点为链表头节点；
        Node curr = zs;
        Node next;
        while (true){
            // 从当前节点打断
            next = curr.next;
            curr.next = null;
            if (!hasCircle(next)){
                curr.next = next;
                return curr.value;
            }
            // 将打断的位置修复，继续下一次遍历
            curr.next = next;
            curr = curr.next;
        }
    }

    /**
     * 判断链表中是否有环(circle)
     *
     * @param zs : 代表头结点
     * @return : 是否有环
     */
    private static boolean hasCircle(Node zs) {
        // 如果链表为空，则返回false
        if (zs == null) return false;
        // 设置快慢双节点，快节点一次两步，慢节点一次一步，如果链表存在环，则快慢双指针迟早会相遇
        Node quick = zs;
        Node slow = zs;
        while (quick.next != null && quick.next.next != null) {
            quick = quick.next.next;
            slow = slow.next;
            if (quick == slow) return true;
        }
        return false;
    }

    /**
     * 求链表的中间元素
     *
     * @param root: 代表一个链表的头结点
     * @return : 中间结点的值
     */
    private static String getMid(Node root) {
        // 设置快慢双指针，快指针2步，慢指针1步，当快指针到达链表尾部时，慢指针即为中间
        Node quick = root;
        Node slow = root;
        while (quick.next != null && quick.next.next != null) {
            quick = quick.next.next;
            slow = slow.next;
        }
        return slow.value;
    }

}
